#include<bits/stdc++.h>
using namespace std;

//definition for singly-linked list.
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
	ListNode* partition(ListNode* head, int x) {
		ListNode* dummy = new ListNode();
		dummy->next = head;
		ListNode* left = dummy, * right = dummy;
		ListNode* lNext, * rNext;
		bool flag = true;
		while (right->next)
		{
			if (right->next->val >= x) {
				right = right->next;
				flag = false;
			}
			else if (flag) {
				left = left->next;
				right = right->next;
			}
			else {
				lNext = left->next;
				rNext = right->next->next;
				left->next = right->next;
				left->next->next = lNext;
				right->next = rNext;
				left = left->next;
			}
		}
		return dummy->next;
	}
};